#include <stdio.h>

// 带哨兵的线性查找函数
int linear_search_with_sentinel(int arr[], int size, int target)
{
    int last = arr[size - 1]; // 保存数组最后一个元素
    arr[size - 1] = target;   // 将目标值设置为哨兵

    int i = 0;
    while (arr[i] != target)
    { // 不需要检查数组边界
        i++;
    }

    arr[size - 1] = last; // 恢复数组最后一个元素

    if (i < size - 1 || arr[size - 1] == target)
    {             // 检查是否找到目标
        return i; // 返回找到的位置
    }
    return -1; // 未找到返回-1
}

int main()
{
    int data[] = {12, 45, 7, 23, 56};          // 测试数组
    int size = sizeof(data) / sizeof(data[0]); // 计算数组长度

    // 情况1：查找成功
    int target1 = 23;
    int result1 = linear_search_with_sentinel(data, size, target1);

    if (result1 != -1)
    {
        printf("Element %d found at index %d.\n", target1, result1); // 输出查找成功信息
    }
    else
    {
        printf("Element %d not found in the array.\n", target1);
    }

    // 情况2：查找失败
    int target2 = 99;
    int result2 = linear_search_with_sentinel(data, size, target2);

    if (result2 != -1)
    {
        printf("Element %d found at index %d.\n", target2, result2);
    }
    else
    {
        printf("Element %d not found in the array.\n", target2); // 输出查找失败信息
    }

    return 0;
}